Message authentication methods provide the ability of a message recipient communicating with a message sender via an insecure channel to determine whether the message received was, in fact, generated by the message sender. These methods are desirable because an insecure channel allows a party not intended to communicate via the insecure channel (i.e., an adversary) to alter the other parties' messages (sections deleted, rearranged, added to, etc.) and insert messages of their own into the insecure channel. Message authentication methods guarantee the integrity (authenticity) of message data such that an adversary cannot alter a message after it is generated, transmitted on, or stored in, the insecure channel in a way that remains undetected by a message recipient. Authentication methods are also desirable whenever a party stores a set of data on an insecure storage device that can be accessed by other parties which are not intended to alter those data (viz., V. D. Gligor and B. G. Lindsay: “Object Migration and Authentication,” IEEE Transactions on Software Engineering, SE-5 Vol. 6, November 1979).
Message authentication methods were surveyed by A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone in their book “Handbook of Applied Cryptography”, CRC Press, Boca Raton, 1997, incorporated by reference herein. A well-known method for performing message authentication requires that an authentication tag, also known as the Message Authentication Code (MAC), be computed for a message using a block cipher, with a secret key shared by the sender and receiver. The length of the authentication tag, or MAC, is fixed and usually much smaller than that of the message for which it is computed. Upon receipt of a message and its authentication tag, a receiver computes the authentication tag of the received message by applying the block cipher in the same manner as that used by the sender, and compares the computed tag with the received tag. If the two tags are equal, the message is accepted as authentic; otherwise, the message is rejected. The specific procedure for computing and verifying an authentication tag (or MAC) is called the authentication scheme or mode.
It is well-known in the art that aforementioned block ciphers, which have long been established among the cryptographic primitives of choice for implementing general message and data encryption, can be used to implement message authentication schemes. A block cipher uses a key to transform data (plaintext) blocks of fixed length into ciphertext blocks of the same length. Although message authentication schemes exist that use other cryptographic primitives (e.g., hash functions) and do not rely exclusively on block ciphers (viz., J. Black, S. Halevi, H. Krawczyk, T. Krovetz, and P. Rogaway, “UMAC: Fast Message Authentication via Optimized Universal Hash Functions,” Advances in Cryptology—CRYPTO '99, Springer-Verlag, LNCS 1666, 216–233, 1999; and M. Bellare, R. Canetti, and H. Krawczyk, “Keying Hash Functions for Message Authentication,” Advances in Cryptology—CRYPTO '96, Springer-Verlag, LNCS 1109, pp. 1–15, 1996, for some recent examples), authentication schemes that use only block ciphers are both necessary and desirable. They are necessary whenever the block cipher is the only cryptographic primitive available, as it is often the case since (1) block ciphers alone are sufficient, and routinely used, for most cryptographic operations including message encryption, and (2) supporting additional, separate cryptographic primitives (e.g., hash functions) to be used exclusively for message authentication would increase both system complexity and cost. They are desirable whenever the use of block ciphers leads to improved performance of the message authentication scheme, as it is often the case since hardware and firmware support for block-cipher implementation is significantly more widespread and less costly than that for cryptographic primitives specialized for MAC computation and verification (e.g., hardware and firmware support for hash functions).
The best-known authentication scheme based exclusively on block ciphers is the Cipher-Block Chaining Message Authentication Code (CBC-MAC). The CBC-MAC takes as input data a plaintext string x=x1 . . . xn and a secret key K shared by the sender of message x and the intended receiver. Key K is usually chosen uniformly at random. The size of each block xi is l bits and that of key K is k bits. The authentication tag of plaintext x is provided by zn, where zi=FK(xi⊕zi−1), where i=1, . . . , n, z0=O, ⊕ is the bit-wise exclusive-or operation, and FK is the block cipher F using key K (viz., M. Bellare, J. Killian, P. Rogaway: “The security of cipher block chaining,” Advances in Cryptology—CRYPTO '94, LNCS 839, pp. 341–358, 1994). After receiving message x and authentication tag zn′, the receiver computes authentication tag zn of message x and then compares this tag with zn′. Message x is accepted as authentic by the receiver only if the two tags are equal.
A well-known block cipher used to implement the CBC-MAC, as well as other MACs, is provided by the U.S. Data Encryption Standard (DES), which uses a key size k of 56 bits and has both the input and output block sizes l of 64 bits (viz., NBS FIPS Pub 46, titled “Data Encryption Standard,” National Bureau of Standards, U.S. Department of Commerce, January 1977). It is well-known in the art that the CBC-MAC can use other block cipher algorithms, not just that of DES. In particular, the CBC-MAC, as well as other MACs, can be computed with block ciphers representing pseudo-random functions, not just permutations as in the case of DES, thereby allowing more blocks to be processed before changing the shared secret key (viz., M. Bellare, J. Killian, P. Rogaway: “The security of cipher block chaining,” Advances in Cryptology—CRYPTO '94, LNCS 839, pp. 341–358, 1994). Variants of the CBC-MAC have also been proposed for various applications, including the authentication of real-time data sources where (1) message length remains unknown until the entire message is received, and (2) commencing message authentication cannot be deferred until the end of the message (viz., E. Petrank and C. Rackoff: “CBC MAC for Real-Time Data Sources,” manuscript available at http://www.cs.technion.ac.il/{tilde over ( )}erez/publications.html, 1999). Some variants of CBC-MAC have also been adopted as national and international standards (e.g., ANSI X9.9: “Financial Institution Authentication,” 18 pp., 1986).
It is well-known in the art that the main drawback of the CBC-MAC stems from the sequential manner of the authentication tag computation (viz., M. Bellare, R. Guerin, and P. Rogaway, “XOR-MACs: New Methods for Message Authentication Using Finite Pseudo-Random Functions,” Advances in Cryptology—CRYPTO '95, Springer-Verlag, LNCS 963, pp. 15–28; and M. Bellare, R. Guerin, and P. Rogaway, “Method and Apparatus for Data Authentication in a Communication environment,” U.S. Pat. No. 5,757,913, dated 26 May 1998). That is, the restriction of computing the authentication tag sequentially imposed by the CBC-MAC definition severely limits the speed with which the tag can be computed in computer systems and networks where multiple processing units are available for the concurrent (i.e., parallel or pipelined) block-enciphering operations needed by authentication-tag computation. Despite the availability of multiple processing units that can perform these operations concurrently (i.e., in a parallel or in a pipelined manner), the authentication tag produced by the CBC-MAC must be implemented sequentially, as if only one such unit were available. This represents a significant performance disadvantage of the CBC-MAC and of all other authentication schemes based on it.
Another disadvantage of the CBC-MAC, also well-understood in the art, is that the CBC-MAC does not allow incremental computation of a new authentication tag from an old one; e.g., if a small section of a large message or stored data, for instance one l-bit block is updated, the entire computation of the authentication tag must be performed from scratch, as would be necessary for any new message, thereby failing to take advantage of the fact that only a small message area is modified and save the block enciphering operations for unmodified blocks (viz., M. Bellare, S. Goldwasser, and O. Goldreich, “Incremental Cryptography and Applications to Virus Protection,” Proceedings of the 27th Annual Symposium on the Theory of Computing (STOC '95) ACM Press, pp. 45–56, 1995). As a result, a substantial performance loss in incurred as a consequence of any message or stored data update. A further disadvantage of the CBC-MAC, also well-known in the art, is that the CBC-MAC does not allow out-of-order processing of message blocks for the computation and verification of the authentication tag; e.g., if a block of a message arrives at the authentication tag processing unit before the blocks preceding it in the message, the processing unit must wait until all preceding blocks arrive and are processed before processing the block that arrived first. As a consequence, authentication tag processing is delayed, thereby causing slow-downs of message transmission and reception.
Another message authentication scheme well-known in the art, which relies exclusively on a block cipher, is the XOR-MAC (viz., M. Bellare, R. Guerin, and P. Rogaway, “XOR-MACs: New Methods for Message Authentication Using Finite Pseudo-Random Functions,” Advances in Cryptology—CRYPTO '95, Springer-Verlag, LNCS 963, pp. 15–28; and M. Bellare, R. Guerin, and P. Rogaway, “Method and Apparatus for Data Authentication in a Communication environment,” U.S. Pat. No. 5,757,913, dated 26 May 1998.) The message to be sent is partitioned into data blocks consecutively identified by their position in the message; i.e., by identifier 1 for the first data block, identifier 2 for the second, and so on. Each data block is encoded together with its identifier to form an l-bit word, where l is the length of the block cipher input, and is submitted for enciphering. A separate ciphertext block is created that represents the enciphering of a message header, and this ciphertext block and all the other ciphertext blocks obtained from the enciphering of the message words are combined by an bitwise exclusive-or operation to create an authentication tag.
Although the XOR-MAC allows parallel, pipelined, incremental, and out-of-order processing of the authentication tag, it has the fundamental disadvantage that it requires twice as many uses of the block enciphering function as those needed by the CBC-MAC for the same length of the input plaintext string. This implies that (1) in sequential implementation, the XOR-MAC is twice as slow as the CBC-MAC, and even slower than other authentication schemes that do not rely exclusively on block ciphers, such as UMAC (viz., J. Black, S. Halevi, H. Krawczyk, T. Krovetz, and P. Rogaway, “UMAC: Fast Message Authentication via Optimized Universal Hash Functions,” Advances in Cryptology—CRYPTO '99, Springer-Verlag, LNCS 1666, 216–233, 1999) and HMAC (viz., M. Bellare, R. Canetti, and H. Krawczyk, “Keying Hash Functions for Message Authentication,” Advances in Cryptology —CRYPTO '96, Springer-Verlag, LNCS 1109, pp. 1–15, 1996), and (2) in concurrent (i.e., parallel or pipelined) implementation the XOR-MAC is slower than other authentication schemes, such as the UMAC, that can also be implemented in a concurrent manner. As a consequence, use of the XOR-MAC would slow down message transmissions and data storage rates substantially, thereby causing inefficient transmission and storage of information.